package main

import (
	"fmt"
)

//circle

/**
单向环形链表节点
*/
type CircleSingleNode struct {
	no   int
	data interface{}
	next *CircleSingleNode
}

/*
注意：单向环形链表和单向链表的区别是点之一。head 环形的头是要存数据的，单向的是不存数据的
*/

/**
在环形链表的末尾添加新节点
*/
func Add(head *CircleSingleNode, node *CircleSingleNode) {
	//如果当前链表是空的
	if head.next == nil {
		head.no = node.no
		head.data = node.data
		head.next = head
		return
	}
	//当链表不为空的时候
	//借助临时变量temp,去循环最后那个节点
	temp := head
	for true {
		//注意：环形链表要形成环路。最后那个节点的next域肯定是指向head头节点的
		if temp.next == head {
			//修改最后那个节点的next域指向 新添加的那个节点
			temp.next = node
			//为了形成环状,新添加进来的那个节点的next域要指向head头节点
			node.next = head
			break
		} else {
			//继续往后寻找
			temp = temp.next
		}
	}
}

/**
根据编号no顺序添加新节点(升序)
*/
func AddCircleSingleNodeByNo(head *CircleSingleNode, node *CircleSingleNode) {
	//链表为空
	if head.next == nil {
		head.no = node.no
		head.data = node.data
		head.next = head
		return
	}
	//借助临时变量
	temp := head
	for true {
		if temp.next != head {
			if temp.next.no >= node.no {
				node.next = temp.next
				temp.next = node
				break
			} else {
				temp = temp.next
			}
		} else {

			temp.next = node
			node.next = head
			//说明已经走到环形链表的末尾了，直接在末尾添加新节点
			break
		}
	}
}

/**
根据编号删除指定节点
注意：如果删除成功了会重新返回头结点
*/
func DeleteCircleSingleNodeByNo(head *CircleSingleNode, no int) *CircleSingleNode {

	/*
		删除环形单向链表的思路：
		1.temp先指向head节点，helper指向最后一个节点
		2.让 temp.no和要删除的no比较，如果相同，则同helper完成删除（这里必须要考虑如果删除的是链表的头结点咋办）
	*/
	temp := head
	helper := head
	if temp.next == nil {
		fmt.Println("环形单链表为空,无法执行删除!")
		return nil
	}
	//如果只有一个节点，
	if temp.next == head {
		temp.next = nil
		return nil
	}

	//将helper到环形链表的最后节点
	for true {
		//说明已经找到环形链表的最后一个节点了
		if helper.next == head {
			break
		}
		helper = helper.next
	}

	//如果有两个及其以上的节点
	//这个变量的作用是标识在下面这个循环中有没有已经执行完删除操作
	flag := true
	for true {
		if temp.next == head {
			//已经到循环链表的最后那个节点了
			//【注意】这儿虽然已经找到了之后这个节点，但是这个节点还并没有temp.no==no做比较
			break
		}
		if temp.no == no {
			if temp == head { //说明删除的是头节点
				head = head.next
			}
			//说明已经找到要删除的那个节点
			helper.next = temp.next
			fmt.Printf("删除节点:%d\n", no)
			flag = false
			break
		}
		temp = temp.next     //移动【比较】
		helper = helper.next //移动【一旦找到要删除的节点的helper】
	}

	//这里还要比较一次
	if flag {
		if temp.no == no {
			helper.next = temp.next
			fmt.Printf("删除节点:%d\n", no)
		} else {
			fmt.Printf("未找到节点No:%d\n", no)
		}
	}
	return head
}

/**
顺序显示环形链表
*/
func ShowCircleSingleNode(head *CircleSingleNode) {
	temp := head
	if temp.next == nil {
		fmt.Println("环形链表为空")
		return
	}
	for true {
		fmt.Printf("节点_data:%v,no:%d\n", temp.data, temp.no)
		if temp.next != head {
			temp = temp.next
		} else {
			break
		}
	}
}

/**
初始化一个单向环形链表的节点
*/
func NewCircleSingleNode(value interface{}, no int) *CircleSingleNode {
	node := new(CircleSingleNode)
	node.data = value
	node.no = no
	return node
}

/**
单向环形链表
*/
func main1() {
	head := NewCircleSingleNode("head节点", 1)
	AddCircleSingleNodeByNo(head, head)

	node1 := NewCircleSingleNode("1号节点", 2)
	AddCircleSingleNodeByNo(head, node1)

	node2 := NewCircleSingleNode("2号节点", 3)
	AddCircleSingleNodeByNo(head, node2)

	ShowCircleSingleNode(head)

	//需要接收删除成功后返回的头节点
	head = DeleteCircleSingleNodeByNo(head, 3)
	fmt.Println("显示删除结点后的结果为:")
	ShowCircleSingleNode(head)

}

/**
约瑟夫环问题求解
head:头结点
startNo:从环形链表的第几个节点开始数
m:间隔几个数
*/
func Josephu(head *CircleSingleNode, startNo int, m int) {
	// 1<=k<=n
	//出局的条件：if k==m
	/*
		TODO:k表示 初始化的时候从那个节点开始数，
			比如：k=2;那么就从 环形链表的第二个节点开始数
			那么 temp 就应该指向 环形链表的第二个节点，同时 helper 应该同时移动
			（因为一开始，temp指向头结点，helper指向环形链表的最后一个节点）
	*/

	temp := head
	helper := head
	k := 1 //计数器变量
	if temp.next == nil {
		fmt.Println("环形单链表为空,无法执行删除!")
		return
	}
	if temp.next == head {
		if m > 1 {
			fmt.Println("无法构成出局条件")
			return
		}
	}
	//找链表最后那个节点，将helper指向他
	for true {
		if helper.next == head {
			//找到了，此时helper就是最后那个节点
			break
		} else {
			helper = helper.next
		}
	}

	//寻找开始节点（寻找从那个节点开始数）
	for i := 1; i <= startNo-1; i++ {
		//相当于先空转到开始数数的位置
		temp = temp.next
		helper = helper.next
	}

	for true {
		if k == m {
			//准备出局temp
			//并且重置k==1
			fmt.Printf("出局节点编号:%d\n", temp.no)
			//这里要移除这个节点
			helper.next = temp.next

			temp = temp.next
			k = 1

		} else {
			temp = temp.next
			helper = helper.next
			k = k + 1
		}

		//注意：退出的条件是：链表中只剩一个节点时，输出这个节点然后退出
		if temp == helper {
			fmt.Printf("出局节点编号:%d\n", temp.no)
			temp.next = nil
			break
		}
	}
}

/**
针对求解约瑟夫环问题
*/
func main() {
	head := NewCircleSingleNode(0, 0)
	n1 := NewCircleSingleNode(1, 1)
	AddCircleSingleNodeByNo(head, n1)
	n2 := NewCircleSingleNode(2, 2)
	AddCircleSingleNodeByNo(head, n2)
	n3 := NewCircleSingleNode(3, 3)
	AddCircleSingleNodeByNo(head, n3)
	n4 := NewCircleSingleNode(4, 4)
	AddCircleSingleNodeByNo(head, n4)
	n5 := NewCircleSingleNode(5, 5)
	AddCircleSingleNodeByNo(head, n5)

	fmt.Println("约瑟夫环输出结果:")
	Josephu(head, 2, 3)
}
